package com.dylan.历史.算法.排序;

import com.dylan.历史.util.LogUtil;

import java.util.Arrays;

/**
 * Created by Dylan on 2018/10/23.
 */
public class 基础_排序_希尔排序 {

    public static void main(String[] args) {
        LogUtil.info(Arrays.toString(shellSort(new int[]{3, 6, 2, 7, 2, 6, 8, 0})));
    }

    /**
     * 希尔排序算法 O(nlogn)
     * 先计算一个较大的步长，之后在步长范围内使用插入排序，然后再减少步长
     * 此算法优先对远距离的元素移动，最后使用步长为1，对所有元素再进行一次插入排序
     */
    static int[] shellSort(int[] arr) {
        int len = arr.length;
        int h = 1;
        while (h < len / 3) {
            h = h * 3 + 1; // 1,4,13,40,121,364,...
        }
        while (h >= 1) {
            insertSort(arr, h);
            h = h / 3;
        }
        return arr;
    }

    /**
     * 指定步长的插入排序
     */
    static void insertSort(int[] arr, int h) {
        int len = arr.length;
        for (int i = h; i < len; i++) {
            // 将a[i]插入到a[i-h], a[i-2*h],a[i-3*h]... 之中
            for (int j = i; j - h >= 0 && arr[j] < arr[j - h]; j = j - h) {
                int temp = arr[j];
                arr[j] = arr[j - h];
                arr[j - h] = temp;
            }
        }
    }
}
